'''
https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/description/
'''
from collections import deque
from typing import List


class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        q = deque()
        distance = [[float('inf')] * n for _ in range(m)]
        distance[0][0] = 0
        q.append((0, 0))
        while q:
            x, y = q.popleft()
            for direction in [1, 2, 3, 4]:
                tx, ty = (x, y + 1) if direction == 1 else \
                    (x, y - 1) if direction == 2 else \
                    (x + 1, y) if direction == 3 else (x - 1, y)
                if 0 <= tx < m and 0 <= ty < n:
                    cost = 0 if grid[x][y] == direction else 1
                    if distance[x][y] + cost < distance[tx][ty]:
                        distance[tx][ty] = distance[x][y] + cost
                        if cost == 0:
                            q.appendleft((tx, ty))
                        else:
                            q.append((tx, ty))
        return distance[m - 1][n - 1]
